1122. Relative Sort Array.go

package leetcode

import"sort"

// 解法一 桶排序，时间复杂度 O(n^2)
funcrelativeSortArray(A, B []int) []int {
count:= [1001]int{}
for_, a:=rangeA {
count[a]++
 }
res:=make([]int, 0, len(A))
for_, b:=rangeB {
forcount[b] >0 {
res=append(res, b)
count[b]--
 }
 }
fori:=0; i<1001; i++ {
forcount[i] >0 {
res=append(res, i)
count[i]--
 }
 }
returnres
}

// 解法二 模拟，时间复杂度 O(n^2)
funcrelativeSortArray1(arr1 []int, arr2 []int) []int {
leftover, m, res:= []int{}, make(map[int]int), []int{}
for_, v:=rangearr1 {
m[v]++
 }
for_, s:=rangearr2 {
count:=m[s]
fori:=0; i<count; i++ {
res=append(res, s)
 }
m[s] =0
 }
forv, count:=rangem {
fori:=0; i<count; i++ {
leftover=append(leftover, v)
 }
 }
sort.Ints(leftover)
res=append(res, leftover...)
returnres
}